#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0010.py
@time: 2021/9/12 19:49
@desc: https://leetcode-cn.com/problems/valid-parenthesis-string/
'''
class Solution:
    """
    栈解法
    """
    def checkValidString(self, s: str) -> bool:
        left_stack = []
        star_stack = []
        for i, item in enumerate(s):
            if item=='(':
                left_stack.append(i)
            elif item=='*':
                star_stack.append(i)
            else:
                if len(left_stack)>0:
                    left_stack.pop()
                elif len(star_stack)>0:
                    star_stack.pop()
                else:
                    return False

        while len(left_stack)>0 and len(star_stack)>0:
            left_idx = left_stack.pop()
            star_idx = star_stack.pop()
            if left_idx > star_idx:
                return False

        return len(left_stack)==0


class Solution02:
    """
    dp 解法
    """
    def checkValidString(self, s: str) -> bool:
        # dp 解法
        n = len(s)
        dp = [[False for i in range(n)] for j in range(n)]

        # 单独一个*是合法字符串
        for i in range(n):
            if s[i] == '*':
                dp[i][i] = True

        # 检测每个相邻字符是否可构成合法字符串
        for i in range(1, n):
            c1, c2 = s[i - 1], s[i]
            dp[i - 1][i] = (c1 == '(' or c1 == '*') and (c2 == ')' or c2 == '*')

        # 开始dp
        i = n - 3
        while i >= 0:
            # 当子串(i,j)长度大于2时，检测是否存在dp[i+1][j-1]为true
            c1 = s[i]
            for j in range(i + 2, n):
                c2 = s[j]
                # 检测1：若子串(i,j)的两头（s[i]、s[j]）本身合法，就只需考虑子串(i+1, j-1)是否合法就好
                if (c1 == '(' or c1 == '*') and (c2 == ')' or c2 == '*'):
                    dp[i][j] = dp[i + 1][j - 1]

                # 检测2：若检测1没有坐实，则再检查(i, j)之间是否存在某个k值分割区间使得两边都合法
                if not dp[i][j]:
                    for k in range(i, j):
                        dp[i][j] = dp[i][k] and dp[k + 1][j]
                        if dp[i][j]:
                            break

            i -= 1

        # 最终只需检查完整区间即可
        return dp[0][n - 1]


if __name__ == '__main__':
    s = Solution()
    s2 = Solution02()
    # inp = "(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())"
    inp = "(*)"
    t = s.checkValidString(inp)
    t = s2.checkValidString(inp)
    print(t)